// 给定一个二叉树，找出其最小深度
// 最小深度是从根节点到最近叶子节点的最短路径上的节点数量

// 思路1：层序遍历，当遇到一个node，没有left和right时，返回统计的深度
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，queue的大小

function minDepth(root) {
    if (!root) {
        return 0
    }
    let queue = [root]
    let minDepths = 0
    while (queue.length) {
        let len = queue.length
        minDepths++
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            if (!node.left && !node.right) {
                return minDepths
            }
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return minDepth
}

// 思路2：后序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function minDepth2(root) {
    if (!root) {
        return 0
    }
    if (!root.left && !root.right) {
        return 1
    }
    if (!root.left) {
        return minDepth2(root.right) + 1
    }
    if (!root.right) {
        return minDepth2(root.left) + 1
    }
    return Math.min(minDepth2(root.left), minDepth2(root.right)) + 1
}
const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
    },
};

console.log(minDepth(root));
console.log(minDepth2(root));